
//2392.给定条件下构造矩阵
class Solution {
public:
    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions,vector<vector<int>>& colConditions) {
        // 将行和列分开处理,先确定行的关系,在确定列的关系  
        vector<int> row; // 数组记录上下顺序,数组从小到大 向上
        vector<int> col; // 数组记录左右顺序,数组从小到大 向右

        //使用函数记录从下往上和,从右往左的数据
        function<void(vector<int>&,vector<vector<int>>&)> turn =[&](vector<int>& dir,vector<vector<int>>& condition) 
        {
            unordered_map<int, int> low; // 记录每个数其下面或右边还有几个没有排序的数据
            unordered_map<int, vector<int>> up; // 记录每个数下面或右边还有几个数据
            for (auto& tmp : condition)   
            {
                int a = tmp[0], b = tmp[1];  
                low[a]++;
                up[b].push_back(a);
            }
            queue<int> q; // 记下面没有数字的数
            for (int i = 1; i <= k; i++) {
                if (low.count(i) == 0) {
                    q.push(i);
                    dir.push_back(i);
                }
            }

            while (!q.empty()) 
            {
                int sz = q.size();
                for (int i = 0; i < sz; i++) 
                {
                    int a = q.front();
                    q.pop();
                    auto& nums = up[a];
                    for (auto x : nums)  
                    {
                        if (--low[x] == 0)   //如果下面的数据都已经排好序了,当前位置也可以进行排序了
                        {
                            dir.push_back(x);
                            q.push(x);
                        }
                    }
                }
            }
        };
        
        turn(row,rowConditions);  //统计从下往上的顺序
        turn(col,colConditions);   //统计从右往左的顺序
        
        if(row.size()!=k||col.size()!= k) return {};

        unordered_map<int,int> r;   //使用两个map确定每个数的横纵做横纵坐标位置
        unordered_map<int,int> l;
        for(int i=0;i<k;i++)
        {
            r[row[i]]=k-1-i;  //因为是从下往上的,从右往左的,所以最终结果要反过来
            l[col[i]]=k-1-i;
        }
        vector<vector<int>> ret(k,vector<int>(k));
        for(int i=1;i<=k;i++)
            ret[r[i]][l[i]]=i;

        return ret;
    }
};
